The present invention relates to the process of load balancing in a multiprocessor system.
A multiprocessor system includes a number of central processing units (CPUs) and memories, which typically communicate through a communication network. For example, in an exemplary system, nodes containing CPUs and memories are organized in a two-dimensional grid, wherein each node can communicate with neighboring nodes (in north, east, south or west directions). Furthermore, CPUs can process tasks simultaneously, thereby increasing the overall performance of the computer system.
To fully utilize the processing power of a multiprocessor system, it is important to balance the load between these CPUs. If the load in a multiprocessor system is unbalanced, some CPUs may have a large number of tasks to process while others are idle. In contrast, in a load-balanced system, as many CPUs as possible are kept busy, which allows the system to achieve a near-optimal performance.
Unfortunately, a system may have unbalanced load even when tasks are assigned to the CPUs at the same rate. This is because a task can split into multiple tasks, which are placed at the end of the queue for the CPU working on the task. Hence, even if at one point of time all the queues are of the same length, their lengths may grow uneven as time progresses.
One approach to the load-balancing problem is to use a centralized load balancer which monitors the load of all the queues and assigns tasks accordingly. However, such a centralized entity presents a single point of failure, which is undesirable for a large-scale system requiring high reliability.
Hence, what is needed is a method and an apparatus that performs load balancing without the above mentioned problems.